package InterviewQuestions.interview2;

import offer.TreeNode;
import org.w3c.dom.NodeList;

/**
 * @Author: wangliuyang
 * @Date: 2021/6/3 16:04
 * @Description: 给定一个二叉树的头节点head，路径的规定有以下三种不同的规定：
 * <p>
 * 1）路径必须是头节点出发，到叶节点为止，返回最大路径和
 * <p>
 * 2）路径可以从任何节点出发，但必须往下走到达任何节点，返回最大路径和
 * <p>
 * 3）路径可以从任何节点出发，到任何节点，返回最大路径和
 *
 * 4)路径可以从任何节点出发，到叶节点为止，返回最大路径和
 */
public class Solution7 {
    static int maxSum = Integer.MIN_VALUE;

    /**
     * 路径必须是头节点出发，到叶节点为止，返回最大路径和
     * @param node
     * @return
     */
    public static int maxPathLength1(TreeNode node) {
        if ((node.right == null && node.left == null)) {
            return node.val;
        }
        if (node.right == null) {
            return maxPathLength1(node.left) + node.val;
        }
        if (node.left == null) {
            return maxPathLength1(node.right) + node.val;
        }
        return Math.max(maxPathLength1(node.right), maxPathLength1(node.left)) + node.val;
    }
    /**
     * 路径必须是头节点出发，到叶节点为止，返回最大路径和
     * @param node
     * @return
     */
    public static int maxPathLength2(TreeNode node) {
        if (node == null) return 0;
        Process(node, 0);
        return maxSum;
    }

    public static void Process(TreeNode node, int pre) {
        if (node.left == null && node.right == null) {
            maxSum = Math.max(pre + node.val, maxSum);
        }
        if (node.left != null) {
            Process(node.left, pre + node.val);

        }
        if (node.right != null) {
            Process(node.right, pre + node.val);
        }
    }

    /**
     * 从任意节点向下走，求路径最大和
     *
     * @param node
     * @return
     */
    public static int maxPathLength3(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return process2(node).allTreeMaxSum;
    }

    /**
     * Desc:树形套路问题，分为情况有头节点和没有头节点
     *
     * @param node
     * @return {@link Info}
     * @author wangliuyang
     * @date
     */
    public static Info process2(TreeNode node) {
        if (node == null) {
            return null;
        }
        Info left = process2(node.left);
        Info right = process2(node.right);
        int p1 = Integer.MIN_VALUE;
        //第一种可能性,和头节点无关，最大长度在左边
        if (left != null) {
            p1 = left.allTreeMaxSum;
        }
        //第二种可能性,和头节点无关，最大长度在右边
        int p2 = Integer.MIN_VALUE;
        if (right != null) {
            p2 = right.allTreeMaxSum;
        }
        //第三种可能性,和头节点有关，最大长度为头节点
        int p3 = node.val;
        //第四种可能性,和头节点有关，最大长度经过头节点在左边
        int p4 = Integer.MIN_VALUE;
        if (right != null) {
            p4 = node.val + left.fromaHeadMaxSum;
        }
        int p5 = Integer.MIN_VALUE;
        //第五种可能性,和头节点有关，最大长度经过头节点在右边
        if (right != null) {
            p5 = node.val + right.fromaHeadMaxSum;
        }
        Info info = new Info();
        info.allTreeMaxSum = Math.max(Math.max(Math.max(Math.max(p1, p2), p3), p4), p5);
        info.fromaHeadMaxSum = Math.max(Math.max(p3, p4), p5);
        return info;
    }

    /**
     * 要求子树需要返回的值
     */
    static class Info {
        int allTreeMaxSum; //返回当前树最大值
        int fromaHeadMaxSum;//返回以节点为头节点的最大值
    }


    public static int maxPathLength4(TreeNode node){
        if (node == null) {
            return 0;
        }
        return process3(node).allTreeMaxSum;
    }
    /**
     * Desc:树形套路问题，分为情况有头节点和没有头节点
     *
     * @param node
     * @return {@link Info}
     * @author wangliuyang
     * @date
     */
    public static Info process3(TreeNode node) {
        if (node == null) {
            return null;
        }
        Info left = process2(node.left);
        Info right = process2(node.right);
        int p1 = Integer.MIN_VALUE;
        //第一种可能性,和头节点无关，最大长度在左边
        if (left != null) {
            p1 = left.allTreeMaxSum;
        }
        //第二种可能性,和头节点无关，最大长度在右边
        int p2 = Integer.MIN_VALUE;
        if (right != null) {
            p2 = right.allTreeMaxSum;
        }
        //第三种可能性,和头节点有关，最大长度为头节点
        int p3 = node.val;
        //第四种可能性,和头节点有关，最大长度经过头节点在左边
        int p4 = Integer.MIN_VALUE;
        if (right != null) {
            p4 = node.val + left.fromaHeadMaxSum;
        }
        int p5 = Integer.MIN_VALUE;
        //第五种可能性,和头节点有关，最大长度经过头节点在右边
        if (right != null) {
            p5 = node.val + right.fromaHeadMaxSum;
        }
        int p6 = Integer.MAX_VALUE;
        if (right != null && left != null) {
            p6 = right.fromaHeadMaxSum + node.val + left.fromaHeadMaxSum;
        }
        Info info = new Info();
        info.allTreeMaxSum = Math.max(Math.max(Math.max(Math.max(Math.max(p1,p6), p2), p3), p4), p5);
        info.fromaHeadMaxSum = Math.max(Math.max(p3, p4), p5);
        return info;
    }

    /**
     * 从任意节点开始，到叶节点为止，返回最大路径和
     * @return
     */
    public static int max = Integer.MAX_VALUE;

    /**
     * 此方法返回以当前为头节点的最大路径，然后从所有头节点中选出最大的
     * @param node
     * @return
     */
    public static int maxPathLength5(TreeNode node){
        if(node.left == null && node.right == null) {
            max = Math.max(node.val, max);
            return node.val;
        }
        int nextMax = Integer.MIN_VALUE;
        if (node.left != null) {
             nextMax = maxPathLength5(node.left);
            max = Math.max(max,nextMax);
        }
        if (node.right != null) {
            max = Math.max(nextMax,maxPathLength5(node.right));
            max = Math.max(max,nextMax);
        }
        max = Math.max(nextMax + node.val,max);
        return nextMax + node.val;
    }
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(5);
        TreeNode treeNode2 = new TreeNode(-5);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(1);
        TreeNode treeNode5 = new TreeNode(7);
        TreeNode treeNode6 = new TreeNode(5);
        TreeNode treeNode7 = new TreeNode(-5);
        TreeNode treeNode8 = new TreeNode(-3);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.right = treeNode4;
        treeNode3.left = treeNode5;
//        treeNode4.right = treeNode6;
        treeNode4.left = treeNode7;
        treeNode7.left = treeNode8;
        System.out.println(maxPathLength1(treeNode1));
        System.out.println(maxPathLength2(treeNode1));
        System.out.println(maxPathLength3(treeNode1));
        System.out.println(maxPathLength4(treeNode1));
    }
}
